"""
快速排序

分而治之（divide and conquer，D&C）

使用D&C解决问题的过程包括两个步骤（解决问题的思路）：
    1.找出基线条件，这种条件必须尽可能简单。
    2.不断将问题分解（或者说缩小规模），知道符合基线条件。

D&C的工作原理：
    1.找出简单的极限条件。
    2.确定如何缩小问题的规模，使其符合基线条件。

快速排序：
    快速排序的性能高度依赖于你选择的基准值。

小结：
    1.D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元素的数组。
    2.实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n * log n)
    3.大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
    4.比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)快得多。
"""

from random import randint


def sum_num(num_list):
    """
    求和
    """

    if not num_list:
        return 0

    return num_list[0] + sum_num(num_list[1:])


def count_num(num_list):
    """
    求元素数
    """
    if not num_list:
        return 0

    return 1 + count_num(num_list[1:])


def max_num(num_list):
    """
    求最大数
    """

    if len(num_list) == 2:
        return num_list[0] if num_list[0] > num_list[1] else num_list[1]

    sub_max = max_num(num_list[1:])
    return num_list[0] if num_list[0] > sub_max else sub_max


def quick_sort(arr):
    """
    快速排序
    """

    if len(arr) < 2:
        # 基线条件
        return arr
    else:
        # 递归条件
        # 基准值
        pivot = arr[0]
        # 小于等于基准值的元素组成的子数组
        less = [i for i in arr[1:] if i <= pivot]
        # 大于基准值的元素组成的子数组
        greater = [i for i in arr[1:] if i > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)


if __name__ == "__main__":
    nums = [i for i in range(1, 10)]

    # 求和
    print(sum_num(nums))

    # 求元素数
    print(count_num(nums))

    # 求最大数
    print(max_num(nums))

    # 快速排序
    nums = [randint(1, 50) for i in range(1, 100)]
    print(quick_sort(nums))
